﻿//#include <stdio.h>
//#include <string.h>
//#include <malloc.h>
//typedef struct
//{
//    int weight;         
//    int parent, lc, rc; 
//} HTNode, * HuffmanTree;
//void Select(HuffmanTree* HT, int n, int* s1, int* s2)
//{
//    int minum, i;     
//    for (i = 1; i <= n; i++)   
//    {
//        if ((*HT)[i].parent == 0)
//
//        {
//            minum = i;
//            break;
//        }
//    }
//    for (i = 1; i <= n; i++)
//    {
//        if ((*HT)[i].parent == 0)
//            if ((*HT)[i].weight < (*HT)[minum].weight)
//                minum = i;
//    }
//    *s1 = minum;    
//    for (i = 1; i <= n; i++)
//    {
//        if ((*HT)[i].parent == 0 && i != *s1)
//        {
//            minum = i;
//            break;
//        }
//    }
//    for (i = 1; i <= n; i++)
//    {
//        if ((*HT)[i].parent == 0 && i != *s1)
//            if ((*HT)[i].weight < (*HT)[minum].weight)
//                minum = i;
//    }
//    *s2 = minum;
//}
//void CreatHuff(HuffmanTree* HT, int* w, int n);
//int main()
//{
//    HuffmanTree HT;
//    int* w, n, wei, i;
//    //printf("input the number of node\n");    
//    scanf("%d", &n);
//    //w = new int[n+1];   
//    w = (int*)malloc((n + 1) * sizeof(int));
//    //printf("\ninput the %dth node of value\n", n);     
//    for (i = 1; i <= n; i++)
//    {
//        scanf("%d", &wei);
//        w[i] = wei;
//    }
//    CreatHuff(&HT, w, n);
//    return 0;
//}
//void CreatHuff(HuffmanTree* HT, int* w, int n) 
//{
//    int m, i;
//    int s1, s2;
//    m = 2 * n - 1;
//    (*HT) = (HTNode*)malloc((m + 1) * sizeof(HTNode));
//    for (i = 1; i <= n; i++) 
//    {
//        (*HT)[i].weight = w[i];
//        (*HT)[i].parent = 0;
//        (*HT)[i].lc = 0;
//        (*HT)[i].rc = 0;
//    }
//    for (i = n + 1; i <= m; i++) 
//    {
//        (*HT)[i].weight = 0;
//        (*HT)[i].parent = 0;
//        (*HT)[i].lc = 0;
//        (*HT)[i].rc = 0;
//    }
//    for (i = n + 1; i <= m; i++) 
//    {
//        Select(HT, i - 1, &s1, &s2);
//        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
//        (*HT)[s1].parent = i;
//        (*HT)[s2].parent = i;
//        (*HT)[i].lc = s1;
//        (*HT)[s2].rc = s2;
//        printf("%d(%d,%d),", (*HT)[i].weight, (*HT)[s1].weight, (*HT)[s2].weight);
//    }
//}